// 二分查找
// 方法一：使用一次二分查找，找到target后，就while循环向前向后找左右边界，最后返回（最差的时间复杂度是O(n)
// 方法二：使用两次二分查找，第一次二分找左边界，第二次二分找右边界
//      第一次把“找第一个等于 target 的下标”变成“找第一个 ≥ target 的下标”
//      第二次把“找最后一个等于 target 的下标”变成“找最后一个 ≤ target 的下标”
class Solution {
    public int[] searchRange(int[] nums, int target) {
//        int left = 0, right = nums.length-1;
//        int[] ret = {-1, -1};
//        while (left <= right) {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] > target) {
//                right = mid-1;
//            } else if (nums[mid] < target) {
//                left = mid+1;
//            } else {
//                int cur = mid; // 找到target
//                // 向前找左边界
//                while (cur >= 0 && nums[cur] == target) cur--;
//                ret[0] = cur+1;
//                cur = mid;
//                // 向后找右边界
//                while (cur < nums.length && nums[cur] == target) cur++;
//                ret[1] = cur-1;
//                break;
//            }
//        }
//        return ret;

        int left = 0, right = nums.length - 1;
        int[] ret = {-1,-1};
        if(nums.length == 0) return ret;
        // 找左边界
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if(nums[left] == target) ret[0] = left;

        // 找右边界
        left = 0; right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        if(nums[left] == target) ret[1] = left;
        return ret;
    }
}